class Solution {
public:
    string addBinary(string a, string b) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i = a.size() - 1;
        int j = b.size() - 1;
        int carry = 0;
        string ans;
        while(i >= 0 || j >= 0 || carry) {
          if(i >= 0) {
            carry += a[i] - '0';
            --i;
          }
          if(j >= 0) {
            carry += b[j] - '0';
            --j;
          }
          ans += (char)(carry % 2 + '0');
          carry /= 2;
        }
        if(ans.size() == 0) {
          ans += '0';
          return ans;
        } else {
          reverse(ans.begin(), ans.end());
          return ans;
        }
    }
};